PD ROM 1

home *** CD-ROM | disk | FTP | other *** search

/ PD ROM 1 / PD ROM Volume I - Macintosh Software from BMUG (1988).iso / Graphics / Graphic Demos / Super MandelZoom / Fractals / Super MZ doc part 1 < prev next >

Wrap

Text File | 1986-12-31 | 26.1 KB | 646 lines | [TEXT/ttxt]

%skip 5 Super MANDELZOOM for the Apple Macintosh by Robert P. Munafo %skip 15 Abstract The Mandelbrot Set and a program for plotting pictures of it are described. The program presents a simple, modeless user interface which allows the user to easily select the desired region to plot on the screen, adjust the settings and shading tables used to draw it, and select portions of the image to be drawn in greater detail. The user may select a point in the image and obtain its count value, the period of its attractor and a plot of its Julia curve. The program has highly optimized math routines, and a sophisticated executive which prioritizes the execution of multiple commands from the user. %page Mathematical Background ------------ ---------- The Mandelbrot Set is named after mathematician Benoit B. Mandelbrot, who discovered it during his research of a class of fractals called the Julia fractal curves. Mandelbrot describes the Julia curves and the Mandelbrot Set (which he calls the "µ map") in his book, The Fractal Geometry of Nature (W.H. Freeman, 1983). --- ------- -------- -- ------ The Mandelbrot Set is a connected set in the domain of complex numbers, the boundary of which is a fractal curve. (I will often refer to complex numbers as "points" because it is convenient to think of the complex numbers as points on the complex number plane.) For each complex number C, a sequence of "iterates" Z is n defined as follows: Z = 0 + 0 i for n = 0 (1a.) n 2 Z = Z + C for n > 0 (1b.) n n-1 The complex number C is a member of the Mandelbrot Set if and only if lim |Z | (2) n->∞ | n| is finite. The bars indicate the magnitude of Z , that is, n |Z | 2 2 | n| = sqr ( a + b ) (3) where a is the real component and b the imaginary component of Z . (I will refer to points in the Mandelbrot Set n as "member points.") In practice, some large value "n_max" is chosen and Z is used as an approximation to n_max (2) above. For most member points, Z will converge to an attractor, a repeating sequence of values. The n "period" of a point is the number of distinct points in the point's attractor. If the computer is used to draw a picture showing all member points in black and all others white, the result is a large solid black region, which Mandelbrot calls a "µ-molecule", with several much smaller solid black regions nearby, each of which is a miniature of the main solid black region. A µ-molecule is a solid black cardiod-shaped figure with an infinite number of solid black circles touching it but not overlapping it or each other. (Mandelbrot describes a µ-molecule as "the union of an infinite number of maximal connected sets," each of which is called a "µ-atom" and any two of which share at most one point between them.) The point of contact between two µ-atoms is called a "bond". Although they appear to be seperate, all the µ-molecules are connected to each other by infinitely thin "tendrils" of member points which do not belong to any µ-molecule, and whose iterates don't converge to an attractor. This alone makes for an interesting picture on the computer screen. However, in this program (and in most other Mandelbrot Set programs) the image is made more interesting by assigning colors to non-member points according to "how quickly" their iterates of Z diverge to infinity. The method most commonly used is to define a quantity called the "count" to be the highest value of n for which |Z | < 4 (4) | n| and then assign a different color to each possible value of the count (that is, one color for each positive integer.) This creates a striking set of concentric bands of different colors. Different colors are assigned to different bands in such a way as to make desired bands stand out, or to make all bands blend together as the user wishes. The boundaries between consecutive bands are actually the solutions to a class of functions called the "leminiscates." For each positive integer n there if a leminiscate L (C) corresponding to the nth band in the n picture. The first five leminiscates are as follows: L (C) = C (5a.) 1 2 L (C) = C + C (5b.) 2 4 3 2 L (C) = C + 2 C + C + C (5c.) 3 8 7 6 5 4 3 2 L (C) = C + 4 C + 6 C + 6 C + 5 C + 2 C + C + C (5d.) 4 16 15 14 13 12 11 10 9 8 7 L (C) = C + 8 C + 28 C + 60 C + 94 C + 116 C + 114 C + 94 C + 69 C + 44 C 5 (5e.) 6 5 4 3 2 + 26 C + 14 C + 5 C + 2 C + C + C L (C) = 4 is a perfect circle, L (C) = 4 is an ellipse, and L (C) = 4 is a sort of pear-shaped figure. The 1 2 3 higher-ordered leminiscates generate increasingly convoluted curves which approach the Mandelbrot Set as a limit. The way in which they do this is extremely elaborate, and they produce beautiful pitures when plotted on the computer screen. %page Macintosh MANDELZOOM --------- ---------- When the user runs Super MANDELZOOM, it displays the viewing window on the left, and several sets of controls on the right. It then begins drawing a picture of the Mandelbrot Set. At any time, the user may: • Scroll the image in any direction; • Zoom in or out by a factor of two, or zoom out by a factor of 16; • Select a portion of the image, zoom in and make that portion fill the whole window; • Select a portion of the image and tell the program to draw that portion at higher resolution before it continues evaluating the rest of the image; • Select the value of n_max (options allow 100, 250, 500, or 1000); • Select the amount of precision to use in computing points (16-bit, 18-bit, 30-bit or 32-bit math); • Select one of six pre-defined shading tables (the program will redraw the picture quickly before continuing with the evaluation of points); • Modify the current shading table; • Select a point and find out the coordinates of the point, what the period of the attractor for that point is (if it's a member point) or what the value of "count" for that point is; • Select a point and view a plot of the Julia fractal curve corresponding to that point; • Quit the program; • Use the Macintosh system's built-in desk accessories and function keys; • Wait and do nothing. In this case, the program will automatically: 1. redraw the picture (if the user has just selected or modified a shading table,) then 2. finish computing points in the selected portion of the image, then 3. continue computing and drawing every point in the picture. This is done first at very low resolution, then at low resolution, then at medium resolution, etc. until the whole picture has been evaluated at 256x256 resolution. The program has a 256x256 array in which it remembers the value of "count" for all points in the image, so the image can be drawn again quickly with a new shading table. Shading is done with "ordered dithering", which allows a large number of different shades of gray to be displayed in the same image without sacrificing resolution in areas which contain high-contrast boundaries. Seventeen different shades are used. SUPER MANDELZOOM is very fast - in benchmark tests it runs as fast as the equivalent written in C for a dedicated VAX 11/780. This high performance is realized because the program was written and highly optimized in machine language, using 32-bit integer math. The VAX, on the other hand, uses high precision floating-point math; therefore although it is only as fast as the Mac it allows much more magnification. The Mac is even faster (three times as fast) when 16-bit math is used. Benchmarks BEWARE: Like most statictics, benchmarks can be misleading. These times were taken on a 512K Mac with the old (64K) ROMs, without the "Mouse Point" display active or any desk accessories open, and without touching the mouse or keyboard. If you want to compare these times to another Mandelbrot Set program, you must have the settings for the other program exactly as follows: Square picture exactly 0.06250000 units long on each side, centered at exectly - 0.91656494 + 0.26464843 i, with maximum number of iterations equal to 500. Note that on machines with hardware color table mapping it won't take any time at all to "redraw" the picture. This image is the one on the front cover of the August 1985 Scientific American. Resolution 32 bits 30 bits 18 bits 16 bits Redraw Picture ---------- ---------- ---------- ---------- ---------- -------------- 16x16 6.6 sec. 4.8 sec. 4.7 sec. 2.6 sec. 0.5 sec. 32x32 24.5 17.7 16.6 8.5 1.2 64x64 93.6 66.7 63.3 29.4 3.4 128x128 243.1 174.6 168.6 79.3 9.2 256x256 732.5 525.4 508.8 239.9 27.5 Based on this example, 256x256 is 3.02 times faster than 128x128, and 16-bit math is 3.06 times faster than 32-bit math. The reason 256x256 doesn't take 4 times longer than 128x128 is explained under the sub-heading "_IDLE_MODE" in the "Program Implementation" section below. Using the Program ----- --- ------- Scrolling The four arrows arranged like IBM cursor-control keys are for scrolling. Each will move by a distance equal to 1/8 the size of the window and begin evaluating the section which has just "scrolled in". If you scroll while the computer is redrawing the picture (which happens when changing the shading table or using desk accessories, see below) it will begin redrawing the picture again. Zoom In and Zoom Out There are five large icons immediately adjacent to the scrolling arrows. Clockwise from upper-right, they are "Home", "Zoom Out 16", "Zoom Out 2", "Select and Zoom In", and "Zoom In 2". Zoom In 2 and Zoom Out 2 change the size of the image by a factor of two. Home sets the center and size to the values they have when the program first starts. Zoom Out 16 zooms out four times, increasing the size by a factor of 16. (Note that the size can never be greater than 4.) The Select and Zoom control is used as follows: 1. Click on the icon. The cursor will change to indicate the Mac is now waiting for you to select the region. (When you select Query, Julia, or Detail (explained below,) the cursor will change back to normal.) 2. Press down the mouse button on the point which is to become the center of the picture. Keep the mouse button pressed down. 3. Move the mouse in any direction. A square outline indicates what size the selection will be; move the mouse around to specify the correct size. (The minimum allowed is 1/16 the width of the current picture; the mazimum allowed is twice the width of the current picture.) 4. Release the mouse button. The Mac will begin computing the new image. The default size for Select and Zoom is 1/16 - that is, if you just click the mouse and release it without moving, it will zoom in by a factor of 16. If you do this by accident, you can quickly restore the correct size (but not the correct center position) with the Zoom Out 16 icon. Query Below the icons used for zooming in and out are three more large icons used for special commands. The one on the left has a crosshairs cursor with a question mark next to it. This is called the "Query" command. If you select this icon, then click on a point in the image with the mouse, the program will show: 1. the coordinates of the point; 2. the value of "count" for that point (if it is a member point, this value is infinity) 3. an arrow indicating which line in the shading table window (see below) corresponds to this value of "count" 4. the period of the attractor for the point (if the point is a non-member point, this is undefined.) This figure will not always be correct. The closer a point is to the edge of a µ-atom, the harder it is to determine the period. For many points it is unsure about the period and will put a question mark after the answer. For other points it will report a value which is incorrect (in these cases, the value will not have a question mark, and it will always be a multiple of the correct value.) For many more points Query will give no value at all -- often in these cases the point is not actually a member point. Julia Next to the Query command icon is an icon with a small picture of a Julia Fractal curve. Select this icon, then select a point in the image and the computer will draw in the picture window an outline of the Julia curve corresponding to the point. The method for producing a picture of a Julia curve is quite different from that for drawing the Mandelbrot Set images - the picture is drawn in high resolution, but quite faintly (lots of points missing) at first, and more and more well-defined the longer you wait. You will have to click the mouse to make the computer stop drawing the Julia curve and continue with the Mandelbrot Set image from where it left off. The algorithm used to compute the Julia curve is not very precise, and usually generates several (or many) random isolated points which do not really "belong" to the Julia curve in question. Detail Next to the Julia curve icon is an icon showing a low-resolution Mandelbrot Set image with a rectangular portion in high resolution. This is the "Detail" command. Select the icon, then select a rectangular region in the image (do this the same way you draw a rectangle in MacPaint.) The program will then draw everything inside the rectangle at twice the resolution it is currently drawn in. When it is done doing this, it will resume evaluating the rest of the image. This command can be very useful - suppose you're viewing a complex area of the Mandelbrot Set using 30-bit math, n_max = 1000, and there is one area (say a small spiral-shaped feature near the bottom) which you are waiting to see in high resolution. 30-bit math is very slow, and since the spiral is at the bottom you might have to wait as much as half an hour before it is drawn even at 128x128 resolution. Using the Detail command you can have the computer work on the spiral right away. Other things you should know about this command: • If you select another rectangle before the computer is done doing the first, the computer will stop doing the one it was working on, and will not go back to it unless you select it again later. • When you select or edit a shading table (see below,) the computer begins redrawing the picture with the new shading table. You can select a rectangle while the computer is redrawing the picture, but it won't actually start evaluating the points in the rectangle until it is done redrawing the picture. (Redrawing is fast, so this shouldn't be much of a problem.) • Detail can be run as many times as you want on any area of the image. Suppose that areas "A" and "B" are currently drawn in 8x8 pixels. After selecting "A", it will be drawn in 4x4 pixels. Select area "A" again and it will be drawn in 2x2 pixels. Then select areas "A" and "B" at the same time - area "A" will drawn in 1x1 pixels, and area "B" will be drawn in 4x4 pixels. • If a large percentage of points in the rectangular area you select are member points, Detail will be noticably slower. The reason for this is that member points take a lot of iterations to compute. You can make Detail run faster by avoiding member points, i.e. by dividing the region of interest into two or more pieces, each of which has relatively few member points in it. Beware, however - if you avoid ALL of the member points, you might miss small features which are close to the Mandelbrot Set but which are not visible unless drawn in high resolution. • If you have a 128K Mac, Detail should be used to examine the ends of "cusps" and display the tip if it was missed by the main evaluation routine. (On a 512K Mac these features will be found automatically by the _Q_SEARCH routine.) For an explanation of this and of the "adjacency algorithm" which allows the program to avoid computing almost all "black points", read the sub-heading "_IDLE_MODE" in the Program Structure ~~~~~~~ ~~~~~~~~~ section near the end of this documentation. Set n_max Below the three large command icons are four small buttons labelled "100", "250", "500", and "1000". These are for choosing n_max, i.e. the maximum number of iterations to be used in evaluating a point. Note that when you change n_max, the picture buffer is cleared, and the program has to recompute all points from scratch. Set Number of Bits Below these are four more small buttons labeled "16", "18", "30", and "32". These select how many bits (binary digits) of accuracy to use in computations. 16 bits is fastest (by far,) 18 bits and 30 bits are both about twice as slow, and 32 bits is three times as slow as 16. In general, you should use the fastest setting which is allowed given the current level of magnification that you're using. This table provides a general guideline: size magnification use relative time ------------------------ -------------------- ------- ------------- 4.0 down to .015 1 to 256 16 bits 1.00 .0078 512 18 bits 2.12 .0039 down to .00000095 1024 to 4,194,304 30 bits 2.19 .00000023 8,388,608 32 bits 3.05 The program will display an asterisk (*) after the value of the size for the current plot if you are not using sufficiently precise math to get an accurate plot at 256x256 resolution. This guideline is not always right - in a few areas of the Mandelbrot Set it seems necessary to use one or two more bits of resolution than shown here. (I have not been able to determine precisely which areas these are, but they seem to occur mostly near cusps in areas near the leftmost part of the Mandelbrot set.) The "relative time" is based on the benchmarks above. Note that 18-bit math is almost as slow as 30-bit math, and is useful at only one level of magnification. Similarly, 32-bit math is almost 40% slower than 30-bit math but is only useful at one level of magnification. Because of this, it is usually most convenient to use only the 16 and 30 bit modes and not worry about the other two. Like "zoom" and "set n_max" commands, changing the number of bits causes the picture buffer to be cleared, and all points to be recomputed from scratch. Select Shading Table To the right of all of these buttons is a vertical row of six large icons labeled "1" through "6". These icons are for choosing which shading table to use. Edit Shading Table Furthest to the right is a long vertical rectangle containing a representation of the currently selected shading table. This is the table editing window and it has two parts. The left side is a blank white area with lots of little black squares in it (exactly one square per row). The right side is a set of horizontal bands of different shades of gray (one band per row.) There are 128 rows in the shading table. Click the mouse in the left-hand side of the editing area and drag the mouse around to set the positions of the little black squares. It may take a little practice to get used to the way this works, but you should get used to it after a short while. When you release the mouse button, it will start redrawing the picture with the modified shading table. The first entry of the shading table (the topmost row) is unused. The next 65 entries correspond to count values from 0 to 64 (one entry per count value.) The next 60 entries after that consist of 30 "blocks" of two entries each. Each block corresponds to 32 count values: the first block for counts from 65 to 96, the next block for 97 to 128, etc. Within each block the first shading table entry is used for all count values which equal one or two modulo four (e.g. 65, 66, 69, 70, 73, 74, etc. ) and the second is used for the rest of the count values. The user should set both values in the block the same to get solid areas, and set them different to get patterns of alternating stripes. The 127th entry in the shading table is unused, and the last entry is used for member points. Mouse-Point Below all of the controls is a small box with the word "Mouse:" next to it. If you click in the box, the coordinates of the point under the cursor will be displayed at all times when the cursor is over the picture. Click in the box again to turn it off. You should use this only when you need it, because it makes the computer continually check the mouse position and therefore slows down the evaluation and drawing of points considerably. This feature should be useful when you know the coordinates of something and want to find it quickly, however, it requires some practice. This is the easiest method I have found to locate areas quickly: Suppose we want to locate the area used for the benchmark example. This is -.916 +.264 i, size = .062. First hit the Home icon, then the Select and Zoom icon. The first time you zoom in, select -.9 +.2i as the center, and zoom in by a factor of eight. Then find -.91 +.26 i and zoom in again, etc. Every time you zoom in by a factor of eight you add one more digit to the coordinates of the point to use as the center of the next selection. Continue this process until you have the required number of digits. (Note that when you "Select and Zoom" it will zoom in by 16 if you just click the mouse on a point. To zoom in by eight you have to click and drag the mouse a little to select the next-larger size square.) Desk Accessories Super MANDELZOOM supports desk accessories. Open them from the Apple menu as in any other program, and use the Cut, Copy, Paste, etc. commands to accomplish editing functions within the D.A.'s. (The Edit menu doesn't do anything when no desk accessories are open.) When you have desk accessories active, the D.A.'s window(s) always remain on top of the program display (but you can still operate Super MANDELZOOM's controls if they are not covered by something.) Desk accessories make the program run significantly slower, so you should have all of them closed when you are not using them. I use the Scrapbook to save images that I have grabbed with CMD-SHIFT-9 (see below). I also use MockWrite to read this documentation - when run from within Super MANDELZOOM, MockWrite (and any other desk accessories that use 9-point Monaco) will display text in a 6-point font. I have tested the Scrapbook, Key Caps, Alarm Clock, Control Panel, MockWrite, Sleep, Utilities and a few others within my program and they seem to work fine. Some desk accessories will crash, often unpredicably. For example, one earlier version of MockWrite I tested caused a System Error (ID=2) when it tried to call SetWTitle on its editing window and inadvertantly passed a nil WindowPtr. Another, called ZoomIdle, occasionally closed Super MANDELZOOM's window, causing its display to disappear permanently. Therefore, if you are going to be using some D.A. within Super MANDELZOOM, you should test it thoroughly first to see if it will crash. Function Keys The four standard function keys (CMD-SHIFT-1, CMD-SHIFT-2, etc.) work in Super MANDELZOOM - I find CMD-SHIFT-3 most useful (it saves the screen to disk as a MacPaint document.) When using a function key, you will often find that the desired effect doesn't happen until you click the mouse somewhere. This is because of an optimization which allows the program to run significantly faster (by not calling GetNextEvent until EventAvail returns true.) In addition to the four standard Macintosh function keys, another (CMD-SHIFT-9) has been added to Super MANDELZOOM. This function key lets you copy a section of the screen to the clipboard. To use it, hit CMD-SHIFT-9, then select a rectangle anywhere on the screen, the same way you do in MacPaint (except you have to start in the upper-left corner and finish in the lower-right corner, otherwise it might crash.) When you have selected a rectangle it will copy that part of the screen to the clipboard as a picture, which can then be pasted into the Scrapbook or whatever. (Note that MacPaint will not let you paste an entire 256x256 image at once. I believe FullPaint will but I haven't had a chance to try it.) FKEY 9 is a public-domain utility. Unfortunately, I don't remember who created it. You can use the Resource Editor to install it in your System files. Special Considerations for Users of 128K Macs, Switcher, Ram Disks, etc. This program tries to allocate a 256x256 array (about 65K of memory) when it starts up. If it cannot allocate this much space, it allocates a 16K array instead and notifys the user. Side-effects of the small array include: • After computing a 256x256 image, the program will redraw the image at only 128x128 resolution when a new shading table is picked, when the current shading table is edited, or after the Help or Julia curve command. To see the image again at 256x256 resolution, the user must force re-evaluation by selecting the whole image (or the area of interest) with the Detail command. • The _Q_SEARCH routine normally used to locate the tips of "cusps" cannot be run on the small array. There- fore, the user has to select the cusps with the Detail command to find anything that was missed. (See the description of _IDLE_MODE below) Users of small Macs might also find that the program bombs when desk accessories are used. Super MANDELZOOM always leaves at least 20K of free space for desk accessories, but this will not be enough for certain D.A.'s or combinations of D.A.'s.